/*
 * @lc app=leetcode.cn id=60 lang=java
 *
 * [60] 排列序列
 */

import java.util.ArrayList;
import java.util.List;
// @lc code=start
class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        boolean[] used = new boolean[n];    // 记录数字是否被使用过

        return dfs(nums, new ArrayList<String>(), used, 0, n, k);
    }

    private String dfs(int[] nums, List<String> level, boolean[] used, int depth, int n, int k) {
        if(depth == n) {
            StringBuilder sb = new StringBuilder();
            for(String s : level) {
                sb.append(s);
            }
            return sb.toString();
        }

        int cur = factorial(n - 1 - depth);

        for(int i = 0; i < n; i++) {
            if(used[i])
                continue;
            
            if(cur < k) {
                k = k - cur;
                continue;
            }

            level.add(nums[i] + "");
            used[i] = true;
            return dfs(nums, level, used, depth + 1, n, k);
        }
        return null;
    }

    // 计算阶乘
    private int factorial(int n) {
        int res = 1;
        for(int i = 1; i <= n; i++) {
            res *= i;
        }
        return res;
    }
}
// @lc code=end

